翻訳と辞書 Words near each other ・ POS端末機 ・ POV〜呪われたフィルム〜 ・ POV～呪われたフィルム～ ・ POWER (ポケットビスケッツの曲) ・ POWER DoLLS Detachment of Limited Line Service プロジェクトα ・ POWER DoLLS～オムニ戦記2540～ ・ POWER GAME〜パワーゲーム〜 ・ POWER OF LOVE (JUDY AND MARYの曲) ・ POホスファチジルコリン ・ POユズマシュ ・ PP (計算複雑性理論) ・ PP -ピアニッシモ- 操リ人形ノ輪舞 ・ PP2 (化合物) ・ PPAR (曖昧さ回避) ・ PPAR-γ ・ PPARγ ・ PPC広告 ・ PPC用紙 ・ PPC複写機 ・ PPD-34/38短機関銃 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク PP (計算複雑性理論) ： ウィキペディア日本語版 PP (計算複雑性理論)[ぴーぴー] 計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械で多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は "probabilistic polynomial time" を意味する。1977年、Gill が定義した〔J. Gill, "Computational complexity of probabilistic Turing machines." ''SIAM Journal on Computing'', 6 (4), pp. 675–695, 1977.〕。 == 概要 == PP に属する決定問題には、コインを投げて無作為に決定を行うアルゴリズムが存在する。その時間計算量は多項式時間以内であることが保証される。解が YES なら、そのアルゴリズムは 1/2 以上の確率で YES を返す。解が NO なら、そのアルゴリズムは最大でも 1/2 の確率で YES を返す。より実用的な観点では、このクラスに属する問題は、無作為ながらも多項式時間である一定の確率で正しい答えを返すので、それを適当な回数繰り返すことで十分な精度で解を得ることができる。 PP は、非決定性チューリング機械で多項式時間で解ける問題の集合と定義することもでき、その場合、計算経路の半数以上で受理されたとき、全体として受理されたと判断する。このため、PP のことを Majority-P と呼ぶことがある〔Lance Fortnow. Computational Complexity: Wednesday, September 04, 2002: Complexity Class of the Week: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html〕。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PP (計算複雑性理論)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.